Visualization of delay propagation segment trees

When there is a discrepancy between the explanation here and the source doc, the source is correct, because I'm regression testing with doctest.

Visualization of [Delayed propagation segment tree

Become a range-action, range-contractible delay propagation segment tree

Here we use the implementation so far as possible, managing the "table of actions not yet applied (delayed) to the values" in a dual segment tree and the "values" separately in a segment tree

The objective is to depict what kind of interaction between these two trees

As a result, range action and downward propagation are difficult to operate on each of the separate tables, so a mechanism was introduced to bundle the two tables together and treat them as a single table.

Initialize the value segment tree normally

code:python

>> set_depth(4)

>> full_up(value_table, lambda x, y: f"{x}{y}")

>> debugprint(value_table)

| abcdefgh |

| abcd | efgh |

| ab| cd| ef| gh|

|a|b|c|d|e|f|g|h|

Initialize the dual segment tree of the action with the unit action

code:python

>> action_unity = PowAction(1)

>> debugprint(action_table)

| ^1 |

| ^1 | ^1 |

| ^1 | ^1 | ^1 | ^1 |

|^1|^1|^1|^1|^1|^1|^1|^1|

Properly define the synthesis of actions

For example, the unit source could be an empty list, and the composite of the action could be a union of lists.

code:python

def action_composite(new_action, old_action):

return PowAction(new_action.value * old_action.value)

I was mistakenly thinking that I could just update the range for the table in action here.

In fact, the value table needs to be updated at the same time.

First define how the value is updated by the action

def action_force(action, value): ...

Next, for a table of action/value pairs, create a function that simultaneously composes the action and updates the value

code:python

def combined_action(new_action):

def f(args):

action, value = args

return (

action_composite(new_action, action),

action_force(new_action, value))

return f

This allows for range action.

(It needs to be propagated from above first, but I'm skipping it because there's nothing to propagate right now.)

At first I misunderstood it as "first only the table of the action is written, then the value is updated and propagated to the children of the action as needed".

Even at the end of the tree, the value needs to be updated, but there are no children to propagate it, so a conditional branching is necessary.

code:python

>> range_update(combined_table, L, R, combined_action(PowAction(2)))

>> debugprint(action_table, 3)

| ^1 |

| ^2 | ^1 |

| ^1 | ^1 | ^2 | ^1 |

| ^1| ^1| ^1| ^1| ^1| ^1| ^1| ^1|

>> debugprint(value_table, 3)

| abcdefgh |

| (abcd)^2 | efgh |

| ab | cd | (ef)^2| gh |

| a | b | c | d | e | f | g | h |

Value updates propagate up segment-tree-like

Operation on only the table of values here, segment tree part

code:python

>> up_propagate(value_table, up(L), lambda x, y: f"{x}{y}")

>> up_propagate(value_table, up(R), lambda x, y: f"{x}{y}")

>> debugprint(value_table, 3)

| (abcd)^2(ef)^2gh |

| (abcd)^2 | (ef)^2gh |

| ab | cd | (ef)^2| gh |

| a | b | c | d | e | f | g | h |

In the following implementation, the propagation path is calculated first and used both up and down.

Upward propagation merges in the middle, so this method is good because it eliminates the merging and beyond.

Next time a range action is performed (from here on, the full version of the range action without abbreviations)

First propagate the delayed action down with respect to both ends of the range

When the action goes down, the lower value is also updated.

To ensure that the action that came first is used to update the value first

I wondered if this could be expressed by propagating downwards in a twin-pair segmented tree, but it was difficult.

After propagation, the parent is implemented back to the unit action, but it is not appropriate for "action/value pairs".

The action returns to the unit action, but the value is not updated.

So I wrote exclusively for it.

code:python

def down_propagate_force(table, pos, action_composite, action_force, action_unity):

max_level = pos.bit_length() - 1

for level in range(max_level):

i = pos >> (max_level - level)

action_composite(action, a),

action_force(action, v))

action_composite(action, a),

action_force(action, v))

Propagate down, then range, then propagate the value up, and so on, all together.

code:python

>> L = 1

>> R = 5

>> down_propagate_force(

... combined_table, up(L),

... action_composite, action_force, action_unity)

>> down_propagate_force(

... combined_table, up(R),

... action_composite, action_force, action_unity)

>> debugprint(action_table)

| ^1 |

| ^1 | ^1 |

| ^1 | ^2 | ^1 | ^1 |

|^2|^2|^1|^1|^2|^2|^1|^1|

>> debugprint(value_table)

| (abcd)^2(ef)^2gh |

| (abcd)^2 | (ef)^2gh |

| (ab)^2| (cd)^2| (ef)^2| gh |

|a^2|b^2| c | d |e^2|f^2| g | h |

>> range_update(combined_table, L, R, combined_action(

... PowAction(3), action_composite, action_force))

>> debugprint(action_table, 3)

| ^1 |

| ^1 | ^1 |

| ^1 | ^6 | ^1 | ^1 |

| ^2| ^6| ^1| ^1| ^6| ^2| ^1| ^1|

>> debugprint(value_table, 3)

| (abcd)^2(ef)^2gh |

| (abcd)^2 | (ef)^2gh |

| (ab)^2 | ((cd)^2)^3 | (ef)^2 | gh |

| a^2 |(b^2)^3| c | d |(e^2)^3| f^2 | g | h |

>> up_propagate(value_table, up(L), lambda x, y: f"{x}{y}")

>> up_propagate(value_table, up(R), lambda x, y: f"{x}{y}")

>> debugprint(value_table, 3)

| a^2(b^2)^3((cd)^2)^3(e^2)^3f^2gh |

| a^2(b^2)^3((cd)^2)^3 | (e^2)^3f^2gh |

| a^2(b^2)^3 | ((cd)^2)^3 | (e^2)^3f^2 | gh |

| a^2 |(b^2)^3| c | d |(e^2)^3| f^2 | g | h |

range contraction

Propagate down and then range-contract normally for a table of values.

code:python

>> L = 3

>> R = 5

>> down_propagate_force(

... combined_table, up(L),

... action_composite, action_force, action_unity)

>> down_propagate_force(

... combined_table, up(R),

... action_composite, action_force, action_unity)

>> debugprint(value_table)

| a^2(b^2)^3((cd)^2)^3(e^2)^3f^2gh |

| a^2(b^2)^3((cd)^2)^3 | (e^2)^3f^2gh |

| a^2(b^2)^3 | ((cd)^2)^3 | (e^2)^3f^2 | gh |

| a^2 |(b^2)^3| c^6 | d^6 |(e^2)^3| f^2 | g | h |

>> value_unity = ""

>> print(range_reduce(value_table, L, R, lambda x, y: f"{x}{y}", value_unity))

d^6(e^2)^3

Consider doing Range add, range sum

If we do (+1) to a node with size 4, the value must increase by 4

Programmatic solution: make the action take node size as an argument, not just value

Mathematical solution: make the domain of the value the direct product of the node size

Since the parent node size is the sum of the child node sizes, it can be properly constructed by propagation upwards

The approach we have taken so far of "expressing by pasting two trees together," only takes a mathematical approach to the table of action-value pairs, since the position and size of the nodes are not passed to the function (combined_action) that simultaneously synthesizes the action and updates the value.

It's about time we don't do it here because the gap between moving it at a realistic speed is getting too big.

The AOJ's four types of delayed propagation segment tree problems are solved by implementing the problem without creating a "table of action-value pairs" and passing both as arguments, so please refer to that.

---